\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\graphicspath{ {../images/} }
\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{第七次上机作业报告}
\author{姓名：殷文良\qquad 学号：3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\section{项目设计思路}
本次上机作业的设计思路参考了The Boost Graph Library (BGL)，关于对各数据结构间关系的理解见图\ref{fig1}。
\begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth]{7_1.png}
  \caption{图的概念和各数据结构关系}
  \label{fig1}
\end{figure}

\begin{enumerate}
\item
  本次作业分别实现邻接表和邻接矩阵两种存储方式，并且在图初始化时，可以让用户指定存储方式。如果用户没有指定，则应该根据图的疏密决定采用哪种方式，常用判断稠密图的条件是
  \begin{equation*}
    m \geq n\log{n},
  \end{equation*}
  其中$m$是边的数量，$n$为顶点的个数。但是，由于本次作业在构造图时并不需要输入顶点个数和边数，而是输入顶点集合，因此并未采用上述判断方法。考虑到实际生活中碰到的图大多数都为稀疏图，因此当用户未指定图的存储方式时，默认以邻接表的方式存储。
\item
  邻接矩阵采用STL中\verb!vector!数据结构实现，通过\verb!vector<vector<double>>!构建矩阵记录边的存在性（无权图）或权重（有权图）；邻接表则采用STL中的\verb!unordered_map!数据结构实现，其中\verb!key!为顶点，\verb!value!为链表，链表的每个元素为一个结构体，记录边的权重和顶点信息。
\item
  模板类Graph可以采用不同类型数据的顶点，比如\verb!int,char!等，Graph类的成员函数见图\ref{fig2}。
  \begin{figure}[H]
  \centering
  \includegraphics[width=0.272\textwidth]{7_2.png}
  \caption{Graph类设计}
  \label{fig2}
\end{figure}
\end{enumerate}


\section{测试说明}
本次上机作业分别对有向有权图、有向无权图、无项有权图和无项无权图四种情况进行测试。
\begin{itemize}
\item
  在shell终端输入\verb!make report!，可以得到上机报告report.pdf；
\item
  在shell终端输入\verb!make(compile)!，可以编译C++程序main.cpp，输入\verb!./test!可在终端得到输出结果；
\item
  在shell终端输入\verb!bash run!，可以将输出结果重定向到文件result.txt中；
\item
  在shell终端输入\verb!make check!，可以检查程序main.cpp的内存泄漏情况。
\end{itemize}

\section{测试结果}
\subsection{程序运行结果}
\begin{enumerate}
\item 有向有权图
  \begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth]{7_3.png}
  \caption{有向有权图}
  \label{fig3}
  \end{figure}
  
  \begin{figure}[H]
  \centering
  \includegraphics[width=0.727\textwidth]{7_7.png}
  \caption{程序运行结果}
  \label{fig7}
  \end{figure}

\item 有向无权图
  \begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth]{7_4.png}
  \caption{有向无权图}
  \label{fig4}
  \end{figure}

  \begin{figure}[H]
  \centering
  \includegraphics[width=0.607\textwidth]{7_8.png}
  \caption{程序运行结果}
  \label{fig8}
  \end{figure}

\item 无向有权图
  \begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth]{7_5.png}
  \caption{无向有权图}
  \label{fig5}
\end{figure}

  \begin{figure}[H]
  \centering
  \includegraphics[width=0.582\textwidth]{7_9.png}
  \caption{程序运行结果}
  \label{fig9}
  \end{figure}

\item 无向无权图
  \begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth]{7_6.png}
  \caption{无向无权图}
  \label{fig6}
  \end{figure}

  \begin{figure}[H]
  \centering
  \includegraphics[width=0.509\textwidth]{7_10.png}
  \caption{程序运行结果}
  \label{fig10}
  \end{figure}
\end{enumerate}


\subsection{内存泄露检查}
图\ref{fig11}说明程序不存在内存泄露的情况。
\begin{figure}[H]
  \centering
  \includegraphics[width=0.774\textwidth]{7_11.png}
  \caption{内存泄漏检查}
  \label{fig11}
\end{figure}

\section{总结}
\subsection{亮点之处}
\begin{enumerate}
\item
  本次作业完成了所有的要求，并且实现了保障安全性的各种功能，比如有权图和无权图增加边调用不同的函数，无向图存在loop，用户重复加边等各种情形，从逻辑上确保了程序的正确性，也避免了用户恶意输入导致程序崩溃。
\item
  在设计邻接矩阵时，增设了invlidWeight成员变量，代表无效权重，缺省值为0。之所以这样做，是因为受教材启发，在不同情形下通过设置该成员的值很大或很小，可以实现求最短路径或最长路径等需求。
\end{enumerate}

\subsection{不足之处}
\begin{enumerate}
\item
  由于C++水平有限，为了实现上述的某些功能，导致某些地方的代码较为臃肿，或许可以从逻辑设计上进行改进。
\item
  在完成了邻接表和邻接矩阵两个类的实现，开始设计Graph类时，遇到了较大的困难。或许更合理的一种思路是：先将Graph基类设置为抽象类，然后邻接表类和邻接矩阵类分别继承该类，最后采用“工厂模式”实现“让用户指定存储方式”的功能。但是碍于麻烦，采用了一种相反的思路，以很不优雅的方式实现了Graph类。
\end{enumerate}


\end{document}
